package com.dy.栈;

import com.dy.栈.链栈.LinkStack;

/**
 * 加数从高位到低位依次入两个栈，并创建结果栈
 * 都非空时，依次弹出栈顶相加，和存入一个变量中;若和有进位，将和的个位压入栈中，将进位加到下一位数字
 * 若某个为空，依次弹出与进位相加，，存入栈
 */
public class 大数加法 {

    public String add(String a, String b) throws Exception {
        LinkStack sum = new LinkStack();
        LinkStack sA;
        LinkStack sB;

        int partialSum;
        boolean isCarry = false;
        sA = numSplit(a);
        sB = numSplit(b);
        while (!sA.isEmpty() && !sB.isEmpty()) {
            partialSum = (Integer) sA.pop() + (Integer) sB.pop();
            if (isCarry) {
                partialSum++;
                isCarry = false;
            }
            if (partialSum >= 10) {
                isCarry = true;
                sum.push(partialSum - 10);
            } else {
                sum.push(partialSum);
            }
        }

        LinkStack tmp = !sA.isEmpty() ? sA : sB;
        while (!tmp.isEmpty()) {
            int t = (Integer) tmp.pop();
            if (isCarry) {
                t++;
                if (t >= 10) {
                    sum.push(t - 10);
                } else {
                    isCarry = false;
                    sum.push(t);
                }
            } else sum.push(t);
        }
        if(isCarry){
            sum.push(1);
        }
        StringBuilder sb = new StringBuilder();
        while(!sum.isEmpty()){
            sb.append(sum.pop());
        }
        return sb.toString();


    }

    LinkStack numSplit(String s) throws Exception {
        LinkStack tmp = new LinkStack();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (' ' == c) continue;
            else if ('0' <= c && '9' >= c) {
                tmp.push(Integer.valueOf(String.valueOf(c)));
            }
        }
        return tmp;
    }

    public static void main(String[] args) throws Exception {
        大数加法 solution = new 大数加法();
        System.out.println(solution.add("9","9999999999991"));
    }

}
